import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map.Entry;
import java.io.*;

class FileWrite 
{
  public void write(String arg)
  {
  try{
  // Create file 
  FileWriter fstream = new FileWriter("map.txt");
  BufferedWriter out = new BufferedWriter(fstream);
  out.write(arg);
  //Close the output stream
  out.close();
  }catch (Exception e){//Catch exception if any
  System.err.println("Error: " + e.getMessage());
  }
  }
}

final class Process {
	private BigInteger fringe, p, g, h, gb;

	public Process() {
		p = new BigInteger("13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171");
				  
		g = new BigInteger("11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568");
				  
		h = new BigInteger("3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333");
				  
				  

		fringe = BigInteger.valueOf(2).pow(20);
		
		gb = g.modPow(fringe, p);
	}
	
	public BigInteger LeftSide(BigInteger x) {
		return g.modPow(x, p).modInverse(p).multiply(h).mod(p);
	}
	
	public BigInteger RightSide(BigInteger x) {
		//return g.modPow(fringe, p).modPow(x, p);
		return gb.modPow(x, p);
	}
	
	public  HashMap<BigInteger, BigInteger> BuildMap() {
		final HashMap<BigInteger, BigInteger> result = new HashMap<BigInteger, BigInteger>();
		BigInteger i = BigInteger.ZERO;
		BigInteger ls;
		while (i.compareTo(fringe) <= 0) {
			ls = LeftSide(i);
			//result.put(i, ls);
			result.put(ls, i);
			System.out.println("i=" + i + ", xxx=" + ls);
			i = i.add(BigInteger.ONE);
		}
		return result;
	}
	
	public static BigInteger getKeyByValue(HashMap<BigInteger, BigInteger> map, BigInteger value) {
	    for (Entry<BigInteger, BigInteger> entry : map.entrySet()) {
	        if (value.equals(entry.getValue())) {
	            return entry.getKey();
	        }
	    }
	    return null;
	}
	
	public  BigInteger LookInMap(HashMap<BigInteger, BigInteger> map) {
		BigInteger i = BigInteger.ZERO;
		BigInteger rs;
		BigInteger key;
		while (i.compareTo(fringe) <= 0) {
			rs = RightSide(i);
			//key = getKeyByValue(map, rs);
			key = map.get(rs);
			if (key != null) {
				return i.multiply(fringe).add(key);
			}
			System.out.println("i=" + i + ", rs=" + rs);
			i = i.add(BigInteger.ONE);
		}
		return null;
	}

}

class Process6 {
	protected BigInteger n, a, p, q, x;

	private static int tryMax(final BigInteger divisor,
	        final BigInteger toDivide) {
	    for (int i = 9; i > 0; i--) {
	        BigInteger div = divisor.multiply(BigInteger.TEN).add(
	                BigInteger.valueOf(i));
	        if (div.multiply(BigInteger.valueOf(i)).compareTo(toDivide) <= 0)
	            return i;
	    }
	    return 0;
	}
	
	public static BigInteger bigSqrt(BigInteger N) {
		 String sqrt = "";
		    BigInteger divisor = BigInteger.ZERO;
		    BigInteger toDivide = BigInteger.ZERO;
		    String Nstr = N.toString(10);
		    if (Nstr.length() % 2 == 1)
		        Nstr = "0" + Nstr;
		    for (int digitCount = 0; digitCount < Nstr.length(); digitCount += 2) {
		        toDivide = toDivide.multiply(BigInteger.TEN).multiply(
		                BigInteger.TEN);
		        toDivide = toDivide.add(new BigInteger(Nstr.substring(digitCount,
		                digitCount + 2)));
		        String div = divisor.toString(10);
		        divisor = divisor.add(new BigInteger(
		                div.substring(div.length() - 1)));
		        int into = tryMax(divisor, toDivide);
		        divisor = divisor.multiply(BigInteger.TEN).add(
		                BigInteger.valueOf(into));
		        toDivide = toDivide.subtract(divisor.multiply(BigInteger
		                .valueOf(into)));
		        sqrt = sqrt + into;
		    }
		    //System.out.println("Sqrt(" + N + ") = \n" + sqrt);
		    return new BigInteger(sqrt);
	 }
	
	public Process6() {
		n = new BigInteger("179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581");
		a = bigSqrt(n).add(BigInteger.ONE);
		System.out.println(a);
		System.out.println(a.pow(2));
		System.out.println(a.pow(2).subtract(n));
		x = bigSqrt(a.pow(2).subtract(n));
		System.out.println("x=" + x);
		p = a.subtract(x);
		q = a.add(x);
		System.out.println("n=" + n + ",\nx=" + p.multiply(q));
		System.out.println("p=" + p + ",\nq=" + q);

	}
	


}

final class Process6a extends Process6 {
	public Process6a() {
		n = new BigInteger("648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877");
		a = bigSqrt(n).add(BigInteger.ONE);
		System.out.println(a);
		System.out.println(a.pow(2));
		System.out.println(a.pow(2).subtract(n));
		x = bigSqrt(a.pow(2).subtract(n));
		System.out.println("x=" + x);
		p = a.subtract(x);
		q = a.add(x);
		while (!p.multiply(q).equals(n)) {
			a = a.add(BigInteger.ONE);
			x = bigSqrt(a.pow(2).subtract(n));
			p = a.subtract(x);
			q = a.add(x);
			System.out.println("x=" + x);
		}
		System.out.println("n=" + n + ",\nx=" + p.multiply(q));
		System.out.println("p=" + p + ",\nq=" + q);

	}
}

final class Process6b extends Process6 {
	public Process6b() {
		n = new BigInteger("720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929");
		BigInteger three = BigInteger.valueOf(3);
		BigInteger n24 = n.multiply(BigInteger.valueOf(24));
		BigInteger a2 = bigSqrt(n24).add(BigInteger.ONE);
		//a = bigSqrt(n6)..add(BigInteger.ONE);
		System.out.println("a^2-6n="+a2.pow(2).subtract(n24));
		//System.out.println(a);
		//System.out.println(a.pow(2));
		//System.out.println(a.pow(2).subtract(n));
		x = bigSqrt(a2.pow(2).subtract(n24)).divide(BigInteger.valueOf(2));
		System.out.println("!!!x=" + x);
		p = a2.divide(BigInteger.valueOf(2)).subtract(x).divide(three);
		q = n.divide(p);
		System.out.println("n=" + n + ",\nx=" + p.multiply(q));
		System.out.println("p=" + p + ",\nq=" + q);
		System.out.println("n-pq=" + n.subtract(p.multiply(q)));
		p = a2.divide(BigInteger.valueOf(2)).add(x).divide(three);
		q = n.divide(p);
		System.out.println("n=" + n + ",\nx=" + p.multiply(q));
		System.out.println("p=" + p + ",\nq=" + q);
		System.out.println("n-pq=" + n.subtract(p.multiply(q)));
		/*while (!p.multiply(q).equals(n)) {
			a2 = a2.subtract(BigInteger.ONE);
			x = bigSqrt(a2.pow(2).subtract(n24)).divide(BigInteger.valueOf(2));
			p = a2.divide(BigInteger.valueOf(2)).subtract(x).divide(three);
			q = n.divide(p);
			if (p.multiply(q).equals(n)) {
				System.out.println("Finished");
				System.out.println("n=" + n + ",\nx=" + p.multiply(q));
				System.out.println("p=" + p + ",\nq=" + q);
				return;

			}
			System.out.println("n-pq=" + n.subtract(p.multiply(q)));
			p = a2.divide(BigInteger.valueOf(2)).add(x).divide(three);
			q = n.divide(p);
			if (p.multiply(q).equals(n)) {
				System.out.println("Finished");
				System.out.println("n=" + n + ",\nx=" + p.multiply(q));
				System.out.println("p=" + p + ",\nq=" + q);
				return;

			}
			System.out.println("n-pq=" + n.subtract(p.multiply(q)));
			System.out.println("x=" + x);
		}*/
		System.out.println("n=" + n + ",\nx=" + p.multiply(q));
		System.out.println("p=" + p + ",\nq=" + q);

	}
}

final class Process6c extends Process6 {
	public Process6c() {
		super();
		BigInteger e = BigInteger.valueOf(65537);
		BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)); 
		BigInteger d = e.modInverse(phi);
		BigInteger c = new BigInteger("22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540");
		String result = c.modPow(d, n).toString(16);
		String plainText = result.split("00")[1];
		String decrypted = new BigInteger(plainText, 16).toByteArray().toString();
		//String plainText = plainText.
		System.out.println(result + '\n' + result.indexOf("00") + '\n' + plainText + '\n' + decrypted);
	}
}
public class HelloWorldClass {
	
	
	static public void solvePAWeek5() {
		Process process = new Process();
		FileWrite fw = new FileWrite();
		HashMap<BigInteger, BigInteger> map = process.BuildMap();
		fw.write(map.toString());
		BigInteger result = process.LookInMap(map);
		System.out.println("Result: " + result);		
	}
	
	static public void solvePAWeek6() {
		//Process6 process = 
		new Process6c();
		
	}
	/**
	 * @param args
	 */
	static public void main(String[] args) {
		solvePAWeek6();
		// TODO Auto-generated method stub
		/* BigInteger	mod(BigInteger m) 
          Returns a BigInteger whose value is (this mod m).
 BigInteger	modInverse(BigInteger m) 
          Returns a BigInteger whose value is (this-1 mod m).
 BigInteger	modPow(BigInteger exponent, BigInteger m) 
          Returns a BigInteger whose value is (thisexponent mod m).
          */
		//final BigInteger a;
		/*BigInteger good = BigInteger.valueOf(2000000000);
		//HashMap<BigInteger, BigInteger> map = BuildMap();
        System.out.println();
        System.out.println("good     = " + good);
        System.out.println("good.add(BigInteger.ONE) = " + good.add(BigInteger.ONE));
        System.out.println("good.multiply(BigInteger.valueOf(3)) = " + good.multiply(BigInteger.valueOf(3)));
        System.out.println("good.multiply(BigInteger.valueOf(4)) = " + good.multiply(BigInteger.valueOf(4)));

		System.out.println("Hello world!");*/

	}
	 /*public static BigInteger bigSqrt(BigInteger N) {
		 String sqrt = "";
		    BigInteger divisor = BigInteger.ZERO;
		    BigInteger toDivide = BigInteger.ZERO;
		    String Nstr = N.toString(10);
		    if (Nstr.length() % 2 == 1)
		        Nstr = "0" + Nstr;
		    for (int digitCount = 0; digitCount < Nstr.length(); digitCount += 2) {
		        toDivide = toDivide.multiply(BigInteger.TEN).multiply(
		                BigInteger.TEN);
		        toDivide = toDivide.add(new BigInteger(Nstr.substring(digitCount,
		                digitCount + 2)));
		        String div = divisor.toString(10);
		        divisor = divisor.add(new BigInteger(
		                div.substring(div.length() - 1)));
		        int into = tryMax(divisor, toDivide);
		        divisor = divisor.multiply(BigInteger.TEN).add(
		                BigInteger.valueOf(into));
		        toDivide = toDivide.subtract(divisor.multiply(BigInteger
		                .valueOf(into)));
		        sqrt = sqrt + into;
		    }
		    System.out.println("Sqrt(" + N + ") = \n" + sqrt);
		    return new BigInteger(sqrt);
	 }
	 public static void main(String args[]) {
		    BigInteger N = new BigInteger(
		            "17976931348623159077293051907890247336179769789423065727343008115"
		                    + "77326758055056206869853794492129829595855013875371640157101398586"
		                    + "47833778606925583497541085196591615128057575940752635007475935288"
		                    + "71082364994994077189561705436114947486504671101510156394068052754"
		                    + "0071584560878577663743040086340742855278549092581");
		    System.out.println(N.toString(10).length());
		    
		    BigInteger sq = bigSqrt(N);
		    N = N.subtract(sq.multiply(sq));
		    System.out.println(N);
		    N = sq.multiply(sq);
		    sq = bigSqrt(N);
		    N = N.subtract(sq.multiply(sq));
		    System.out.println(N);
		    
		}

		private static int tryMax(final BigInteger divisor,
		        final BigInteger toDivide) {
		    for (int i = 9; i > 0; i--) {
		        BigInteger div = divisor.multiply(BigInteger.TEN).add(
		                BigInteger.valueOf(i));
		        if (div.multiply(BigInteger.valueOf(i)).compareTo(toDivide) <= 0)
		            return i;
		    }
		    return 0;
		}*/
}
